#include<stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#define  FILEIO
#define Type int

typedef struct stack
{
	Type value;
	struct stack *next;
	struct stack *prev;
}stack,*pStack;

pStack base=NULL;
pStack top=NULL;
pStack popedItem=NULL;

void push(Type item)
{
	pStack newItem;
	if(base == NULL)
	{
		base = (struct stack *)malloc(sizeof(struct stack));
		top=base;
		base->value = item;
	}
	else
	{
		newItem = (struct stack *)malloc(sizeof(struct stack));
		newItem ->value = item;

		top->next = newItem;
		top->next->prev = top;
		top=newItem;
	}
}

/*
1. if top pointer is NULL,which means this stack is empty

*/
pStack pop()
{
	if(top == NULL)
	{
		// do nothing here.
		return NULL;
	}
	else if(top == base)
	{
		popedItem = top;
		top = base = NULL;
	}
	else
	{
		if(popedItem!=NULL)
		{
			free(popedItem);
			popedItem=NULL;
		}

		popedItem = top;
		top=top->prev;
	}
	return popedItem;
}

int stack_main() 
{ 

#ifdef FILEIO
  freopen("stack_in.txt","r",stdin); 
  freopen("stack_out.txt","w",stdout); 
#endif

  int i=0;
  pStack itemPointer;
  for(i=0;i<100000;i++)
  {
	  push(i);
  }

  while((itemPointer = pop())!=NULL)
  {
	  printf("%d\n",itemPointer->value);
  }

#ifdef FILEIO
  fclose(stdin);
  fclose(stdout);
#endif  
  
  return 0; 
}
